﻿using System;
namespace ShortestPaths
{
    public class DijkstraSP
    {
        private DirectedEdge[] edgeTo;
        private double[] distTo;
        private IndexMinPQ<Double> pq;

        public DijkstraSP(EdgeWeightedDigraph G,int s)
        {
            edgeTo = new DirectedEdge[G.V()];
            distTo = new double[G.V()];
            pq = new IndexMinPQ<double>(G.V());

            for (int v = 0; v < G.V(); v++)
            {
                distTo[v] = Double.MaxValue;
            }

            distTo[0] = 0.0;
            pq.Insert(s,0.0);
            while (!pq.IsEmpty())
            {
                Relax(G,pq.DelMIn());
            }
        }

        private void Relax(EdgeWeightedDigraph G, int v)
        {
            foreach (var e in G.Adj(v))
            {
                int w = e.To();
                if (distTo[w] > distTo[v] + e.Weight())
                {
                    distTo[w] = distTo[v] + e.Weight();
                    edgeTo[w] = e;

                    if (pq.Contains(w))
                    {
                        pq.Change(w, distTo[w]);
                    }
                    else
                    {
                        pq.Insert(w,distTo[w]);
                    }

                }
            }
        }
    }
}
